Some solutions to the problem of scheduling jobs on batch processing machines have been proposed in the prior art, which will be described briefly below.
(1) Solution related to batch scheduling: Li, et al. conducted studies on problems of processing jobs on unrelated parallel-batching processing machines. Based on the complexity of the problems, they proposed a heuristic algorithm based on BFLPT to solve these problems.
Specifically, see SCHEDULING UNRELATED PARALLEL BATCH PROCESSING MACHINES WITH NON-IDENTICAL JOB SIZES, by Li X, Huang Y L, Tan Q, et al., Computers&Operations Research, 2013, 40(12):2983-2990.
(2) Solution related to job deterioration: Wang, et al. conducted studies on production scheduling problems in which the processing time of a kind of jobs increases nonlinearly with the processing start time. Based on the nature of the problems, they proposed an optimal algorithm and a heuristic algorithm to solve these problems.
Specifically see 2012. SINGLE-MACHINE SCHEDULING WITH NONLINEARDETERIORATION, by Wang, J., Wang, M., Optimization Letters 6, 87-98.
(3) Solution related to meta-heuristic algorithm: Eusuff, et al. proposed a shuffled frog leaping algorithm in 2003, which is inspired by a predation process of frogs in the natural world. This algorithm generally includes:
step 1: initializing a frog population;
step 2: dividing the entire population into several groups according to a fitness value of each individual;
step 3: performing local search on each group;
step 4: gathering scattered groups together; and
step 5: determining whether a termination condition is satisfied, if so, going to the step 2.
The advantage of this algorithm is that the set operation can enable each individual to perform certain information exchange at each iteration, and this enhances the optimization capacity of the algorithm.
Specifically see 2003. OPTIMIZATION OF WATER DISTRIBUTION NETWORK DESIGN USING THE SHUFFLED FROG LEAPING ALGORITHM, by Eusuff, M. M., Lansey, K. E., Journal of Water Resources Planning&Management 129, 210-225.
By studies on the related technologies, the inventors found that the time for a job is a determined value and the deterioration of the job is rarely considered during studies on the traditional batch scheduling. In addition, in the traditional shuffled frog leaping algorithm, the local search is similar to the particle migration strategy in the particle swarm algorithm, the convergence accuracy is low and easily plunges into the local optimum, and the discrete combinatorial optimization problem cannot be effectively solved. This leads to unreasonable scheduling.